/**
 * Distributable under LGPL license.
 * See terms of license at gnu.org.
 */
package sudokupso;

import java.lang.Math;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
import java.util.Random;
import java.util.Set;
import java.util.TreeSet;

/**
 *
 * @author Alex
 */
public class Particle implements Cloneable {

    /** the sudoku game represented as a matrix */
    public int[][] game;
    public int[][] fixedPart;
    /** Hold the best position this particle has had */
    private Particle localBest;

    private Particle() {
    }

    public Particle(int[][] fixedPart) {

        this.fixedPart = fixedPart;
        game = new int[fixedPart.length][fixedPart.length];
        for (int i = 0; i < game.length; i++) {

            //fixed elements
            List<Integer> rowList = new ArrayList<Integer>();
            for (int j = 0; j < fixedPart.length; j++) {
                if (fixedPart[i][j] != -1) {
                    rowList.add(fixedPart[i][j]);
                }
            }

            //the rest of the elements to put in a line
            LinkedList<Integer> remElements = new LinkedList<Integer>();
            for (int j = 1; j <= game.length; j++) {
                if (!rowList.contains(j)) {
                    remElements.add(j);
                }
            }

            //mix non-fixed elements
            for (int j = 0; j < remElements.size(); j++) {
                int r = (int) (Math.random() * (j + 1));
                int swap = remElements.get(r);
                remElements.set(r, remElements.get(j));
                remElements.set(j, swap);
            }

            //put everything back into line number lineIndex
            for (int j = 0; j < game.length; j++) {
                if (fixedPart[i][j] != -1) {
                    game[i][j] = fixedPart[i][j];
                } else {
                    game[i][j] = remElements.pop();
                }
            }
        }
        this.localBest = this;
    }

    /**
     * Sum of number of unique elements in each row, plus,
     * sum of number of unique elements in each column,
     * plus, sum of number of unique elements in each box.
     *
     * On each row and square there is at least one unique element type
     *
     * @return fitness value
     */
    public long getFitness() {

        //columns have a hard constraint 
        int rowFitness = 0, boxFitness = 0, columnFitness = game.length * game.length;

        Set<Integer> uniqueElem = new TreeSet<Integer>();
        for (int i = 0; i < game.length; i++) {
            uniqueElem.clear();
            for (int j = 0; j < game.length; j++) {
                uniqueElem.add(game[j][i]);
            }
            rowFitness += uniqueElem.size();
        }

        int squareSize = (int) Math.sqrt(game.length);
        for (int i = 0; i < game.length; i += squareSize) {
            for (int j = 0; j < game.length; j += squareSize) {

                uniqueElem.clear();
                for (int k = i; k < i + squareSize; k++) {
                    for (int l = j; l < j + squareSize; l++) {
                        uniqueElem.add(game[k][l]);
                    }
                }

                boxFitness += uniqueElem.size();
            }
        }

        return rowFitness + boxFitness + columnFitness;
    }

    /**
     * Mutate this particle,
     */
    public void mutate() {
        int lineIndex = (int) (Math.random() * 9);
        int startPos;
        //System.out.println( "line : " + (lineIndex + 1));
        do {
            startPos = (int) (Math.random() * 9);
        } while (fixedPart[lineIndex][startPos] != -1);
        //System.out.println( " first val : " + game[ lineIndex ][ startPos ]);
        int endPos;
        do {
            endPos = (int) (Math.random() * 9);
        } while ((fixedPart[lineIndex][endPos] != -1) && (endPos == startPos));

        //System.out.println( " second val : " + game[ lineIndex ][ endPos ]);

        int aux = game[lineIndex][startPos];
        game[lineIndex][startPos] = game[lineIndex][endPos];
        game[lineIndex][endPos] = aux;

    }

    /**
     * Perform a PMX crossover for this object between localBest and globalBest
     *
     * @see http://www.rubicite.com/Genetic/tutorial/crossover5.php
     */
    public void pmxCrossover(Particle globalBest) {
        Random rand = new Random();
        //int rowIndex = rand.nextInt(game.length); //row index on which crossover is performed
        // do it for all rows - better fitness
        for (int rowIndex = 0; rowIndex < game.length; rowIndex++) {
            int sectionStartIndex = 0;
            int sectionLen = 0;
            boolean sectionSelected = false;
            int numberOfRetries = 300;
            //Randomly select a swath of alleles from parent 1 and copy them directly to the child. Note the indexes of the segment.
            while (!sectionSelected && numberOfRetries > 0) {
                sectionLen = rand.nextInt(game.length); //section len from parent 1 which is copied in the child
                // next select start of section
                sectionStartIndex = 0;
                sectionStartIndex = rand.nextInt(game.length - sectionLen);
                boolean fixedPartFound = false;
                for (int i = sectionStartIndex; i < sectionStartIndex + sectionLen; i++) {
                    if (fixedPart[rowIndex][i] != -1) {
                        fixedPartFound = true;
                        break;
                    }
                }
                if (!fixedPartFound) {
                    sectionSelected = true;
                }
                numberOfRetries--;
            }
            if (!sectionSelected) {
                System.out.println("PMX crossover could not be performed on this particle, too many fixed positions?");
                return;
            }
            int[] parent1 = new int[game.length];
            System.arraycopy(globalBest.game[rowIndex], 0, parent1, 0, game.length);
            int[] parent2 = new int[game.length];
            System.arraycopy(this.game[rowIndex], 0, parent2, 0, game.length);
            int[] child = new int[game.length];
            Arrays.fill(child, -1);
            // save the fixed section
            int[] fixedSection = new int[sectionLen];
            System.arraycopy(parent1, sectionStartIndex, fixedSection, 0, sectionLen);
            //copy the fixed part in the child
            System.arraycopy(fixedSection, 0, child, sectionStartIndex, sectionLen);
            //Looking in the same segment positions in parent 2, select each value that hasn't already been copied to the child.
            //For each of these values:
            //System.out.println("start pmx");
            for (int i = sectionStartIndex; i < sectionStartIndex + sectionLen; i++) {
                int parent2Val = parent2[i];
                int originalParent2Val = parent2Val;
                boolean repeatStepI = true;
                while (repeatStepI) {
                    //System.out.println("repeating step i");
                    boolean found = false;
                    for (int j = 0; j < sectionLen; j++) {
                        if (fixedSection[j] == parent2Val) {
                            found = true;
                            break;
                        }
                    }
                    if (found) {
                        repeatStepI = false;
                        break;
                    }
                    //Note the index of this value in Parent 2. Locate the value, V, from parent 1 in this same position.
                    int parent1Val = parent1[i];
                    int parent2Index = 0;
                    //Locate this same value in parent 2.
                    for (int j = 0; j < parent2.length; j++) {
                        if (parent1Val == parent2[j]) {
                            parent2Index = j;
                            break;
                        }
                    }
                    //If the index of this value in Parent 2 is part of the original swath, go to step i. using this value.
                    if (parent2Index >= sectionStartIndex && parent2Index < sectionStartIndex + sectionLen) {
                        parent2Val = parent1Val;
                        continue;
                    }
                    //If the position isn't part of the original swath, insert Step A's value into the child in this position.
                    repeatStepI = false;
                    child[parent2Index] = originalParent2Val;
                }
            }
            // System.out.println("end pmx");
            //Copy any remaining positions from parent 2 to the child.
            for (int i = 0; i < child.length; i++) {
                if (child[i] == -1) {
                    child[i] = parent2[i];
                }
            }
            // copy the child into the current particle at rowIndex
            System.arraycopy(child, 0, game[rowIndex], 0, game.length);
        }
    }

    /**
     * Perform a multi-parental crossover between this object, localBest and globalBest
     *
     * @param globalBest best position the algorithm has had so far
     * TODO should we also pass the as a parameter the social/memory parameters?
     */
    public void crossover(Particle globalBest, int[] mask) {
        for (int i = 0; i < mask.length; i++) {
            crossoverLine(mask, game[i], localBest.game[i], globalBest.game[i]);
        }
    }

    private void crossoverLine(int[] mask, int[] particleLine,
            int[] localBestLine, int[] globalBestLine) {
        for (int i = 0; i < mask.length; i++) {
            if (mask[i] == 1) // particleLine[i] will be the pivot
            {
                swapPositionWithValue(localBestLine, particleLine[i], i);
                swapPositionWithValue(globalBestLine, particleLine[i], i);
            } else if (mask[i] == 2) {
                swapPositionWithValue(particleLine, localBestLine[i], i);
                swapPositionWithValue(globalBestLine, localBestLine[i], i);
            } else {
                swapPositionWithValue(particleLine, globalBestLine[i], i);
                swapPositionWithValue(localBestLine, globalBestLine[i], i);
            }
        }
    }

    private void swapPositionWithValue(int[] line, int value, int pos) {
        if (line[pos] != value) {
            for (int i = 0; i < line.length; i++) {
                if (line[i] == value) {
                    int aux = line[i];
                    line[i] = line[pos];
                    line[pos] = aux;
                    break;
                }
            }
        }
    }

    /**
     * Updates the local best with the current value of the particle, if current fitness is better
     */
    public void updateLocalBest() {
        if (localBest.getFitness() < this.getFitness()) {
            localBest = (Particle) this.clone();
        }
    }

    @Override
    public String toString() {
        StringBuilder builder = new StringBuilder();
        for (int i = 0; i < game.length; i++) {
            for (int j = 0; j < game.length; j++) {
                builder.append(game[i][j] + " ");
            }
            builder.append("\r\n");
        }
        return builder.toString();
    }

    @Override
    public Object clone() {
        Particle p = new Particle();
        p.game = new int[this.game.length][this.game[0].length];
        //p.fixedPart = new int[this.fixedPart.length][this.fixedPart[0].length];
        p.fixedPart = this.fixedPart;
        for (int i = 0; i < this.game.length; i++) {
            for (int j = 0; j < this.game[0].length; j++) {
                p.game[i][j] = this.game[i][j];
            //    p.fixedPart[i][j] = this.fixedPart[i][j]; //do we need this?
            }
        }
        return p;
    }
}
